/**
 * @file src/search/LocalBeam.java
 */
package search;

/** imports */
import datatypes.Map3D;
import datatypes.Point3D;
import datatypes.Tuple;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;
import java.util.Vector;

/**
 * 1) Find highest z value, which means third component of a Point3D
 * 2) Sequence of points visited to reach the highest point on the map
 *    Save this sequence to "seq.txt"
 * Does not look beyond the immediate neighbors of he current state
 */



/**
 * Local beam hill climbing class
 */
public class LocalBeam
{
	
	/**
	 * Climb method for local beam
	 *
	 * @param map A given world map
	 * @param sequences Where to store the progressed sequences
	 * @param k Number of states to keep track of
	 * 
	 * @return Highest evaluation point
	 */
	public static Point3D localBeamHillClimb(Map3D map, Vector<Point3D> sequence, int k) throws Exception
	{
		/**
		 * inner comparator class for Tuple<Point3D, Point3D>
		 */
		final class TupleReverseComparatorZ implements Comparator<Tuple<Point3D, Point3D>>
		{
			/**
			 * Override compare for tuples
			 * 
			 * @param a Tuple A
			 * @param b TupleB
			 * 
			 * @return -1, 0, 1 depending on comparison
			 */
			@Override
			public int compare(Tuple<Point3D, Point3D> tupleA, Tuple<Point3D, Point3D> tupleB)
			{
				Point3D a = tupleA.first;
				Point3D b = tupleB.first;
				
				if (a.getZ() < b.getZ()) { return 1; }
				else if (a.getZ() > b.getZ()) { return -1; }
				return 0;
			}
			
		} // class TupleComparatorZ
		
		/** consistency check */
		if (k <= 0) { throw new Exception("k <= 0 does not make sense!"); }
		
		/** keep track of sequence */
		if (sequence == null) {
			sequence = new Vector<Point3D>();
		} else {
			sequence.clear();
		}

		/** current states */
		Vector<Point3D> currentStates = new Vector<Point3D>();
		currentStates.setSize(k);
		currentStates.trimToSize();
		
		/** generate k initial states with the help of a random number generator */
		{
			Random randomGen = new Random();
			int i = 0; 
			while (i < k) {
				/** get random point of the map */
				Point3D rand = map.get(randomGen.nextInt(map.getSize()));
				/** set i-th random initial state */
				if (!currentStates.contains(rand)) {
					currentStates.setElementAt(rand, i);
					++i;
				}
			}
			
		} // destroy randomGen
		
		/** sort initial states, not really necessary but better output */
		Collections.sort(currentStates);
		
		/** add initial states to sequence list */
		sequence.addAll(currentStates);
		
		/** add magic point3d after initial states */
		sequence.addElement(new Point3D(Integer.MAX_VALUE, 0, 0.0f));
		
		/** create instance of a TupleComparator */
		TupleReverseComparatorZ tupleReverseComparatorZ = new TupleReverseComparatorZ();
		
		/**
		 * storage for all found neighbors + states = complete list, where..
		 * 
		 *  Tuple<Point3D, Point3D>    =    Tuple<"Successor, "Origin">
		 *  
		 *  so that we stil know where they come from after sorting
		 */
		Vector<Tuple<Point3D, Point3D>> completeList = new Vector<Tuple<Point3D, Point3D>>();

		/**
		 *  for main loop we have following variables:
		 *  
		 *  Vector<Point3D> currentStates
		 *  Vector<Point3D> sequence
		 *  TupleComparatorZ tupleComparatorZ
		 *  Vector<Tuple<Point3D, Point3D>> completeList
		 *  
		 */
		
		/** climb loop */
		while (true) {

			/** clear complete list */
			completeList.clear();
			
			/** add current states to complete list */
			for (Point3D s: currentStates) {
				completeList.addElement(new Tuple<Point3D, Point3D>(s, s));
			}
			
			/** add successors to complete list */
			for (Point3D current: currentStates) {
				/** get successors for current state */
				Vector<Point3D> successors = current.getNeighbors();
				
				/** add successors to complete list */
				for (Point3D p: successors) {
					
					boolean existent = false;
					
					/** check if such a successor is already existent */
					for (Tuple<Point3D, Point3D> t: completeList) {
						if (t.first == p) {
							existent = true;
							break;
						}
					}
					if (!existent) { completeList.addElement(new Tuple<Point3D, Point3D>(p, current)); }
				}
				
			} // for
			
			/** select best successors by sorting them according to their z value */
			Collections.sort(completeList, tupleReverseComparatorZ);
			
			/**
			 * test if there was improvement by at least one of the k best successors 
			 * (start with the best)
			 */
			boolean anyImprovement = false;
			
			/** traverse the best k of the complete list */
			for (int i = 0; i < k; ++i) {
				
				Tuple<Point3D, Point3D> tuple = completeList.get(i);
				Point3D successor = tuple.first;
				Point3D origin = tuple.second;
				
				/** test if there was progess of at least one of the best k successors */
				if (successor.getZ() > origin.getZ()) {
					anyImprovement = true; 
					break;
				}
			} // for
			
			/** no progress at all: the best state of the current states is the result */
			if (!anyImprovement) {
				/** select best state of complete list as the result */
				return currentStates.get(0);
			}
		
			/**
			 * Otherwise: select k best of the complete list as new states
			 */
			for (int i = 0; i < k; ++i) {
				/** move on to new states */
				Point3D neigh = completeList.get(i).first;
				currentStates.set(i, neigh);
				
				/** for the sequence list */
				int reverseI = k - 1 - i;
				Point3D reverseNeigh = completeList.get(reverseI).first;
				sequence.addElement(reverseNeigh);

			} // for
			
			/** add magic point3d for each iteration */
			sequence.addElement(new Point3D(Integer.MAX_VALUE, 0, 0.0f));
			
		} // while
		
	} // localBeamHillClimb(Map3D map, Vector<Vector<Point3D>> sequences, int k) throws Exception
		
} // class LocalBeam























